Tags: #◇Computer Science #◇CSOPESY #◇Operating Systems #◇09 - Virtual Memory

CSOPESY 09 - Virtual Memory

◇Overview

Virtual Memory is a revolutionary technique that entirely separates the logical memory (as seen by a process) from the physical memory (the actual RAM hardware). By doing so, a program can possess a virtual address space that is substantially larger than the available physical memory. Only the active portions of the program are loaded into RAM.

This note covers the mechanisms that make virtual memory possible—specifically Demand Paging—and delves into page fault handling, the powerful Copy-on-Write optimization, various Page Replacement Algorithms, and the catastrophic performance collapse known as Thrashing.

◇Key Concepts

Demand Paging & Page Faults

• Demand Paging: A "lazy loading" strategy where pages are brought into memory only when an instruction explicitly accesses them.
• Valid-Invalid Bit: The page table includes a bit indicating if the page is currently in physical memory (Valid) or not (Invalid / on disk).
• Page Fault: If a process accesses an Invalid page, the hardware triggers a trap to the OS. The OS pauses the process, finds a free frame, schedules a disk I/O to load the required page into the frame, updates the page table to Valid, and restarts the interrupted instruction.

Copy-on-Write (COW)

An optimization used primarily during process creation (e.g., the fork() system call in UNIX). Instead of immediately copying all of the parent's memory pages to the child, both processes share the same physical pages marked as "read-only." If either process attempts to modify a shared page, a trap occurs, and the OS creates a duplicate of only that specific page for the modifying process. This saves massive amounts of time and memory.

Page Replacement

When a page fault occurs and physical memory is completely full (no free frames), the OS must evict an existing page to make room.

• The Dirty Bit (Modify Bit): To optimize I/O, the hardware sets a bit whenever a page is written to. If the evicted page is "dirty", it must be written back to the disk. If it is "clean", it can simply be overwritten without a costly disk write.
• Global vs. Local Replacement:
  • Local: A process can only replace pages from its own allocated frames.
  • Global: A process can "steal" a frame from another process. More common as it maximizes overall system throughput, though it makes execution times unpredictable.

Page Replacement Algorithms

1. FIFO (First-In, First-Out): Replaces the oldest page in memory. Extremely simple, but prone to Belady's Anomaly, a paradoxical situation where adding more physical memory frames actually increases the number of page faults.
2. LRU (Least Recently Used): Replaces the page that has not been accessed for the longest time. Assumes the past predicts the future (Locality of Reference). Highly effective and avoids Belady's Anomaly, but hardware implementation (via counters or stacks) is expensive.
3. Optimal (OPT): Replaces the page that will not be used for the longest period in the future. It guarantees the lowest possible page fault rate but is practically impossible to implement since it requires predicting the future. Used strictly as a theoretical benchmark.

Thrashing

• Thrashing occurs when a process is engaged in high-frequency page faulting. The process spends more time paging (waiting for disk I/O) than executing actual instructions.
• If CPU utilization drops due to thrashing, the OS might incorrectly increase the degree of multiprogramming by admitting new processes, which steal more frames, causing a systemic collapse in throughput.
• Working-Set Model: A strategy to prevent thrashing. The OS tracks the Working Set (the set of unique pages heavily accessed in a recent time window $\Delta$). If the total demand for frames by all working sets exceeds the available physical RAM, the OS suspends a process to free up memory and stabilize the system.

◇Algorithms & Formulas

Effective Access Time (EAT) in Demand Paging

Because disk I/O is astronomically slower than RAM, the page fault rate ($p$) dictates performance.

• $ma$: memory access time
• $p$: probability of a page fault ($0 \le p \le 1$)
• EAT = $(1 - p) \times ma + p \times (\text{page fault service time})$
  Takeaway: $p$ must remain extremely close to $0$ to maintain acceptable performance.

Working-Set State

• $WSS_i$: Working set size of process $i$.
• $D = \sum WSS_i$ (Total demand for frames).
• $m$: Total available physical frames.
• Condition for Thrashing: If $D > m$, thrashing is imminent.

◇Code Examples

Simulating FIFO Page Replacement

def fifo_page_replacement(reference_string, num_frames):
    frames = []
    page_faults = 0
    
    for page in reference_string:
        if page not in frames:
            page_faults += 1
            if len(frames) < num_frames:
                frames.append(page)
            else:
                frames.pop(0) # Evict the oldest (First In)
                frames.append(page)
        # print(f"Access {page}: Frames -> {frames}")
        
    return page_faults

ref_string = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(f"FIFO Faults (3 frames): {fifo_page_replacement(ref_string, 3)}")
# Output: 15

◇References & Navigation

• Previous Topic: ◇CSOPESY 08 - Main Memory
• Next Topic: None
• Related Notes: